package week_04;

import org.junit.Test;
import org.junit.internal.builders.JUnit3Builder;
import org.w3c.dom.Node;

import java.util.LinkedList;

public class SingleList<Intager> {
    //记录头节点
    private Node head;
    //记录链表长度
    private int N;


    /**
     * 节点类
     */
    private class Node {
        //data域
        Integer item;
        //next域
        Node next;

        Node before;

        public Node(Integer item, Node next, Node before) {
            this.item = item;
            this.next = next;
            this.before = before;
        }
    }

    /**
     * 构造函数，初始化链表
     */
    public SingleList() {
//        初始化头节点
        this.head = new Node(null, null, null);
//        初始化链表长度
        this.N = 0;
    }

    /**
     * 清空链表
     */
    public void clear() {
        head.next = null;
        this.N = 0;
    }

    /**
     * @return 获取链表长度
     */
    public int length() {
        return N;
    }

    /**
     * 判断链表是否为空
     *
     * @return 返回Boolean值
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 获取i位置的元素
     *
     * @param i 要查找的元素的位置
     * @return 要查找的元素的值
     */
    public Integer get(int i) {
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    /**
     * 向链表中插入元素
     *
     * @param item 要在链表尾部插入的节点
     */
    public void insert(Integer item) {
        Node n = head;
//        从头节点开始一直找到链表尾部
        while (n.next != null) {
            n = n.next;
        }
//        在找到链表末尾的时候创建一个新节点
        Node newNode = new Node(item, null, null);
        n.next = newNode;
        newNode.before = n;
        N++;
    }

    /**
     * 在指定位置插入元素
     *
     * @param i    要插入的节点的位置
     * @param item 要插入的数值
     */
    public void insert(int i, Integer item) {
        Node n = head;
//        找到要插入的位置的前一个节点
        for (int index = 0; index < i - 1; index++) {
            n = n.next;
        }
        Node cur = n.next;
//        为要插入的元素创建一个新节点
        Node newNode = new Node(item, cur, n);
        n.next = newNode;
        cur.before = newNode;
        N++;
    }

    /**
     * 删除链表i处的元素
     *
     * @param i 要删除的节点的位置
     */
    public void remove(int i) {
//        从头节点开始循环找到第i位置
        Node n = head;
//        i前面的一个节点
        for (int index = 0; index < i - 1; index++) {
            n = n.next;
        }
//        第i处节点
        Node cur = n.next;
//        i后面的那个节点
        Node after = cur.next;
        n.next = after;
        N--;
    }

    /**
     * 删除data域为偶数的节点
     */
    public void remove_odd() {
//        从头节点开始循环
        Node n = head;
        while (n.next != null) {
            if (n.next.item % 2 != 0) {
                n = n.next;
                continue;
            } else {
                //当前偶数节点
                Node cur = n.next;
//        偶数节点后面的节点
                Node after = cur.next;
                n.next = after;
                N--;
            }
        }
    }

    /**
     * 在data域为偶数的节点前面插入一个节点，两个节点的data域相同
     */
    public void insertOddBefore() {
        Node n = head;
        while (n.next != null) {
            if (n.next.item % 2 != 0) {
                n = n.next;
            } else {
                //当前偶数节点
                Node cur = n.next;
//                偶数节点后面的节点
//                创建一个新节点
                Node newNode = new Node(cur.item, cur, null);
                n.next = newNode;
                newNode.before = n;
                n = n.next.next;
                N++;
            }
        }
    }

    /**
     * 在data域为偶数的节点后面插入一个节点，两个节点的data域相同
     */
    public void insertOddAfter() {
        Node n = head;
        while (n.next.next != null) {
            if (n.next.next.item % 2 != 0) {
                n = n.next;
            } else if (n.next.item % 2 == 0) {
                n = n.next;
            } else {
                //当前偶数节点
                Node cur = n.next.next;
//                偶数节点后面的节点
//                创建一个新节点
                Node newNode = new Node(cur.item, cur, null);
                n.next.next = newNode;
                newNode.before = n.next;
                n = n.next;
                N++;
            }
        }
    }

    /**
     * 将两个节点的位置先后交换
     *
     * @param i 要交换的节点
     * @param j 与之交换的节点
     */
    public void perversion(int i, int j) {
        Node n = head;
        Node m = head;
        if (i == 0 && j == 1){
            m=m.next;
        }else {
//        找到要交换的节点的前一个节点
            for (int index = 0; index < i - 1; index++) {
                n = n.next;
            }
            for (int index = 0; index < j - 1; index++) {
                m = m.next;
            }
        }

//        1. 用 temp 这个节点存放 j 位置的节点
        Node tempj = new Node(m.next.item, m.next.next, null);
        Node tempi = new Node(n.next.item, n.next.next, null);
//        2. 把 i 位置的节点放到 j 位置去
        Node bf = n.next.next;
        n.next.next = m.next.next;
        m.next = n.next;
//        3. 把 temp 节点放到 i 位置
        n.next = tempj;
        tempj.next = tempi.next;
        if (j - i <= 1) {
            tempi.next=tempi.next.next;
            n.next.next = tempi;
        }

    }

}
